# include <stdlib.h>
# include <stdio.h>
# include <string.h>
typedef int ElementType; // 元素类型 (typedef作用是起别名)
//循环链表
typedef struct Node {
    ElementType data; // 数据域
    struct Node* next; // 指针域
} Node;

Node* InitList() { // 初始化循环链表(返回指针的函数,语法不懂可看菜鸟教程)
    Node* head = (Node*)malloc(sizeof(Node)); // 分配头结点内存
    head->data = 0; // 头结点数据域置0
    head->next = head; // 头结点指针域指向自己，形成循环
    return head; // 返回头结点指针
}

//初始化节点（带节点数据域参数）
Node initListWithData(ElementType e) {
    Node *node = (Node*)malloc(sizeof(Node)); // 分配节点内存
    node->data = e; // 设置节点数据域
    node->next = NULL; // 节点指针域置空
    return *node; // 返回节点
}

//头插法插入元素
int inserHead(Node* head, ElementType e) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点内存
    if (!newNode) { // 内存分配失败
        printf("内存分配失败，无法插入元素\n");
        return 0; // 插入失败
    }
    newNode->data = e; // 设置新节点数据域
    newNode->next = head->next; // 新节点指针域指向当前第一个节点
    head->next = newNode; // 头结点指针域指向新节点
    return 1; // 插入成功
}

//找到链表环的入口节点
Node* findCycleEntry(Node* head) {
    Node* slow = head; // 慢指针
    Node* fast = head; // 快指针

    while (fast && fast->next) { // 快指针和快指针的下一个节点不为空
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步

        if (slow == fast) { // 相遇，说明有环
            Node* p = head; // 从头结点开始
            int count = 1; // 计数器
            while (p->next != slow) { // 两个指针相遇即为环的入口节点
                p = p->next; // 头结点指针走一步
                // slow = slow->next; // 慢指针走一步
                count++; // 计数器加1 
            }
            fast = head; // 快指针重新指向头结点
            slow = head; // 慢指针重新指向头结点
            for (int i = 0; i < count; i++) { // 快指针先走count步
                fast = fast->next;
            }   
            while (fast != slow) { // 两个指针相遇即为环的入口节点
                fast = fast->next; // 快指针走一步
                slow = slow->next; // 慢指针走一步
            }
            return slow; // 返回环的入口节点
        }
    }
    return NULL; // 没有环
}

Node* get_tail(Node* head) {
    Node* p = head; // 指向头结点
    while (p->next != head) { // 遍历到链表末尾
        p = p->next;
    }
    return p; // 返回尾节点指针
}

int length(Node* head){
    int len = 0; // 初始化长度为0
    Node* p = head->next; // 指向第一个节点
    while (p != head) { // 遍历链表，直到回到头结点
        len++; // 长度加1
        p = p->next; // 指向下一个节点
    }
    return len; // 返回链表长度
}


int main() {
    Node* list = InitList(); // 初始化循环链表
    Node* tail = get_tail(list); // 获取链表尾节点
    inserHead(list, 2); // 头插法插入元素2
    inserHead(list, 3); // 头插法插入元素3
    tail = get_tail(list); // 获取链表尾节点
}   

